using System;
using System.Collections.Generic;
using System.Text;

namespace DeflateLib
{
    /// <summary>
    /// Built code lengths based on frequencies. Code lengths are limited.
    /// </summary>
    static class PackageMergeAlgorithm
    {
        internal static int[] Compute(int[] p, int maxCodeLength)
        {
            int[] map = new int[p.Length];
            int[] pSorted = new int[p.Length];
            for (int i = 0; i < map.Length; i++)
            {
                map[i] = i;
            }
            Array.Copy(p, pSorted, p.Length);
            Array.Sort<int, int>(pSorted, map);

            int start = 0;
            while (start < pSorted.Length && pSorted[start] == 0)
            {
                ++start;
            }

            int[] pSortedNonZero = new int[pSorted.Length - start];
            Array.Copy(pSorted, start, pSortedNonZero, 0, pSortedNonZero.Length);
            int[] lengths;
            if (pSortedNonZero.Length == 0)
                lengths = new int[0];
            else if (pSortedNonZero.Length == 1)
                lengths = new int[] { 1 };
            else
                lengths = ComputeInternal(pSortedNonZero, maxCodeLength);

            int[] resultLengths = new int[p.Length];
            for (int i = 0; i < lengths.Length; i++)
            {
                resultLengths[map[i + start]] = lengths[i];
            }
            return resultLengths;
        }

        // p0 <= p1 <= ... <= pn 
        private static int[] ComputeInternal(int[] p, int maxCodeLength)
        {
            int n = p.Length;
            int[][] steps = new int[maxCodeLength][];
            steps[0] = p;
            int[] lastPairs = new int[p.Length / 2];
            for (int j = 0; j < lastPairs.Length; j++)
            {
                lastPairs[j] = p[j * 2] + p[j * 2 + 1];
            }
            for (int i = 1; i < maxCodeLength; i++)
            {
                int[] merge = MergeArrays(lastPairs, p);
                steps[i] = merge;

                lastPairs = new int[merge.Length / 2];
                for (int j = 0; j < lastPairs.Length; j++)
                {
                    lastPairs[j] = merge[j * 2] + merge[j * 2 + 1];
                }
            }

            int[] h = new int[n];
            int lastPairsCount = n - 1;
            for (int i = maxCodeLength - 1; i >= 0; i--)
            {
				int[] step = steps[i];				
                int pairsCount = 0;
                int pIndex = 0;
                for (int j = 0; j < lastPairsCount * 2; j++)
                {
                    if (pIndex < p.Length && p[pIndex] == step[j])
                    {
                        h[pIndex]++;
                        pIndex++;
                    }
                    else
                    {
                        pairsCount++;
                    }
                }
                lastPairsCount = pairsCount;
            }

            return h;
        }

        private static int[] MergeArrays(int[] array1, int[] array2)
        {
            int[] result = new int[array1.Length + array2.Length];
            int i1 = 0, i2 = 0, i = 0;
            while (i1 < array1.Length && i2 < array2.Length)
            {
                if (array1[i1] < array2[i2])
                {
                    result[i++] = array1[i1++];
                }
                else
                {
                    result[i++] = array2[i2++];
                }
            }
            while (i1 < array1.Length)
            {
                result[i++] = array1[i1++];
            }
            while (i2 < array2.Length)
            {
                result[i++] = array2[i2++];
            }
            return result;
        }
    }
}